package Leetcode第一期;

/**
 * @author : K k
 * @date : 10:07 2020/9/12
 */
public class 手撕KMP {

    //s为主串，word为匹配字串
    public int kmp(String s,String word){
        if (s==null||s.length()<word.length()||word.length()==0||s.length()==0){return -1;}

        //计算maxL数组
        int[] maxL=new int[word.length()];
        int[] next=new int[word.length()];
        for (int i=0;i<word.length();i++){
            //双指针判断
            int pre=0;
            int count=0;
            for (int j=1;j<=i;j++){
                //TODO 有问题 判断公共前后缀算法需要更改
                //获取前后缀的第一个公共字符
                if (word.charAt(pre)==word.charAt(j)){
                    pre++;
                    count++;
                }else if (count>0){
                    //若遇到不相等的则回退
                    count=0;
                    pre=0;
                    j--;
                }
            }
            maxL[i]=count;
        }

        //构造next数组  用于存放索引
        next[0]=-1;
        for (int i=0;i<maxL.length-1;i++){
            next[i+1]=maxL[i];
        }

        for (int c : next) {
            System.out.println(c);
        }

        //进行字符串匹配
        int i=0,j=0;
        int ans=0;//存放答案的索引
        while (i<s.length() && j<word.length()){
            if (s.charAt(i)==word.charAt(j)){
                //逐个判断
                i++;j++;
            }else {
                //遇到不符合的情况
                if (j==0){
                    //开头就失败 则移动到下一位重写判断
                    i++;
                }else {
                    //若是其中某个位置
                    int index=next[j];
                    j=index;
                }
            }
        }
        if (j!=word.length()){
            return -1;
        }
        return i-word.length();
    }

    public static void main(String[] args) {
        手撕KMP kmp=new 手撕KMP();
        String s="acabaabcaccaabc";
        String word="abaabcac";
        int index = kmp.kmp(s, word);
        System.out.println(s.substring(index,index+word.length())+"对应索引位置："+index);

    }
}
